package study.biggestsequence;

// 复杂度为O(n^2)。
public class Method2 {
    public static void main(String[] args) {

        double[] array = {1.5, -12.3, 3.2, -5.5, 23.2, 3.2, -1.4, -12.2, 34.2, 5.4, -7.8,1.1,-4.9};
        System.out.print(findBiggestSequence(array));
    }

    public static double findBiggestSequence(double[] array) {
        double maxsum = Double.MIN_NORMAL;
        int maxindex = 0;
        int minindex = 0;
        // 子序列起点位置
        for(int i=0;i<array.length;i++){
            double sum = 0;
            // 子序列终点位置
            for(int j=i; j<array.length; j++){
                sum +=  array[j];

                if(sum > maxsum){
                    maxsum = sum;
                    minindex = i;
                    maxindex = j;
//                    System.out.println(sum);
                }
            }
        }
        System.out.println("子数列最大和:"+maxsum);
        System.out.println("和最大子数列的开始位置:"+ (minindex+1));
        System.out.println("和最大子数列的结束位置:"+(maxindex+1));
        return maxsum;
    }
}
